typedef struct Trie{
    bool isword; // 当前为末尾时，则对应的查找串为单词
    struct Trie *next[26]; // 多叉树
} Trie;

/** Initialize your data structure here. */
Trie *new_node() {
    Trie *me = malloc(sizeof(*me));
    me->isword = 0;   // false
    for (int i = 0; i < 26; i++)
        me->next[i] = NULL;
    return me;
}
Trie* trieCreate() {
    return new_node();
}

/** Inserts a word into the trie. */
// 插入的过程，同时构建和更新树结构
void trieInsert(Trie* obj, char * word) {
    Trie *p = obj;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        int idx = word[i] - 'a';
        if (p->next[idx] == NULL) {
            p->next[idx] = new_node();  // 中间字符
        }
        p = p->next[idx];
    }
    p->isword = 1;  // 最后一个字符，构成完整单词
}

Trie *find(Trie *root,char *word) {
    int len = strlen(word);
    Trie *cur = root;
    for (int i = 0; i < len; i++) {
        int idx = word[i] - 'a';
        if (cur->next[idx] == NULL) return NULL;   // 查找失败
        cur = cur->next[idx];
    }
    return cur;
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char * word) {
    Trie *res = find(obj, word);
    return (res != NULL) && (res->isword);
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char * prefix) {
    return (find(obj, prefix) != NULL);
}

void trieFree(Trie* obj) {
    for (int i = 0; i < 26; i++) {
        if (obj->next[i]) trieFree(obj->next[i]);
    }
    free(obj);
}